The present invention relates to data transmission and more particularly to data transmission systems to verify the identity of the parties transmitting data.
It is well known to communicate data electronically between a pair of correspondents, typically a pair of computer terminals or a personal card and a computer terminal. Widespread use is made of such communication in the banking environment in order to conduct transactions.
To maintain the integrity of such transactions, it is necessary to implement a system in which the identity of the parties can be verified and for this purpose a number of signature protocols have been developed. Such protocols are based upon El Gamal signature protocols using the Diffie Hellman public key encryption scheme. One commonly used cryptographic scheme is that known as RSA but to obtain a secure transmission, a relatively large modulus must be used which increases the band width and is generally undesirable where limited computing power is available. A more robust cryptographic scheme is that known as the elliptic curve cryptosystem (ECC) which may obtain comparable security to the RSA cryptosystems but with reduced modulus.
Basically, each party has a private key and a public key derived from the private key. Normally for data transfer, a message is encrypted with the public key of the intended recipient and can then be decrypted by that recipient using the private key that is known only to the recipient. For signature and verification purposes, the message is signed with the private key of the sender so that it can be verified by processing with the public key of the stated sender. Since the private key of the sender should only be known to the sender, successful decryption with the sender""s public key confirms the identity of the sender.
The El Gamal signature protocol gets its security from the difficulty in calculating discrete logarithms in a finite field. El Gamal-type signatures work in any group including elliptic curve groups. For example given the elliptic curve group E(Fq) then for Pxcex5E(Fq) and Q=aP the discrete logarithm problem reduces to finding the integer a. With an appropriately selected underlying curve, this problem is computationally infeasible and thus these cryptosystems are considered secure.
Various protocols exist for implementing such a scheme. For example, a digital signature algorithm DSA is a variant of the El Gamal scheme. In this scheme a pair of correspondent entities A and B each create a public key and a corresponding private key. The entity A signs a message m of arbitrary length with his private key. The entity B can verify this signature by using A""s public key. In each case however, both the sender, entity A, and the recipient, entity B, are required to perform a computationally intensive operations, typically an exponentiation, to generate and verify the signature respectively. Where either party has adequate computing power this does not present a particular problem but where one or both the parties have limited computing power, such as in a xe2x80x9cSmart card xe2x80x9d application, the computations may introduce delays in the signature and verification process.
There are also circumstances where the signor is required to verify its own signature. For example in a public key cryptographic system, the distribution of keys is easier than that of a synmnetric key system. However, the integrity of public keys is critical. Thus the entities in such a system may use a trusted third party to certify the public key of each entity. This third party may be a certifying authority (CA), that has a private signing algorithm ST and a verification algorithm VT assumed to be known by all entities. In its simplest form the CA provides a certificate binding the identity of an entity to its public key. This may consist of signing a message consisting of an identifier and the entity""s authenticated public key. From time to time however the CA may wish to authenticate or verify its own certificates.
As noted above, signature verification may be computationally intensive and to be completed in a practical time requires significant computing power. Where one of the correspondents has limited computing capacity, such as the case where a xe2x80x9csmart cardxe2x80x9d is utilized as a cash card, it is preferable to adopt a protocol in which the on card computations are minimized. Likewise, where a large number of signatures are to be verified, a rapid verification facility is desirable.
It is therefore an object of the present invention to provide a signature and verification protocol that facilitates the use of limited computing power for one of the correspondents and verification of the signature.
In general terms, the present invention provides a method of generating and verifying a signature between a pair of correspondents each of which shares a common secret integer comprising the steps of generating from a selected integer a session key at one of the correspondents, selecting a component of said session key and encrypting a message with said selected component, generating a hash of said selected component, and computing a signature component including said common secret integer, said hash and said selected integer and forwarding the signature component, encrypted message and has to the other correspondent. The selected integer may be recovered for the signature component using the common secret integer and the session key encrypted. The balance of the recovered session key may then be used to provide authorized and,. optionally, a challenge to the recipient.